import java.util.HashSet;
import java.util.Set;

public class missingNumber {
//    数组nums包含从0到n的所有整数，但其中缺了一个。
//    请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
//    利用异或的特性，res = res ^ x ^ x。对同一个值异或两次，那么结果等于它本身，
//    所以我们对res从0-nums.length进行异或，同时对nums数组中的值进行异或，出现重复的会消失，
//    所以最后res的值是只出现一次的数字，也就是nums数组中缺失的那个数字。

    public int missingNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
           res ^= i;
           res ^=nums[i];
        }
        res ^= nums.length;
        return res;
    }
    //方法二、哈希表法
    public int missingNumber2(int[] nums){
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i <nums.length ; i++) {
              set.add(nums[i]);//将数组中的元素存入哈希表中
        }
        int miss = -1;//存放哈希表中没有出现的元素
        for (int i = 0; i <=nums.length; i++) {
            if(!set.contains(i)){//遍历0到nums.length找出没有出现的元素
                miss = i;
                break;
            }
        }

        return miss;
    }
    public static void main(String[] args) {
        int [] nums = new int[]{0,1,2,3,4,6};
       missingNumber M = new missingNumber();
      int re = M.missingNumber(nums);
        System.out.println(re);
    }
}
